/**
 * @author Kevin
 * @Data 2021/4/29
 */
public class KMP_test {
    public static void main(String[] args) {
        String str = "aaba";
        int [] array = getNext(str);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
    public static int[] getNext(String str){
        int[] next = new int[str.length()];
        next[0] = 0;
        int k = 0;
        int i = 1;
        while (i < str.length()-1){
            if(k == 0 || str.charAt(k) == str.charAt(i)){
                k = k+1;
                next[i] = k;
                k++;
                i++;
            }else{
                k = next[k];

            }
        }
        return next;
    }
}
